import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Main2 {


    public static int isNiceNumber(int n) {
        //
        if (n % 2 == 0) {
            return 1;
        } else {
            //
            int x = (int)Math.sqrt(n);
            if (x * x == n) {
                return 1;
            } else {
                return 0;
            }

        }
    }


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int count = in.nextInt();//数据组数
            while (count > 0) {
                count --;
                int n = in.nextInt();//数组长度
                int q = in.nextInt();//提问次数

                int[] arr = new int[n+1];//创建数组，长度为n
                int[] flg = new int[n+1];
                for (int i = 1; i <= n; i++) {
                    arr[i] = in.nextInt();
                    flg[i]=flg[i-1]+isNiceNumber(arr[i]);

                }






                while (q > 0) {
                    q--;
                    int l = in.nextInt();
                    int r = in.nextInt();//提问区间
                    System.out.println(flg[r]-flg[l-1]);
                }

            }

        }
    }
}